There are several known computer applications that require graphic objects to be transformed from vector representation to raster representation. For example, such a transformation is needed to display graphic objects on a display device, such as a computer monitor, or to display graphic objects on a page using a printing device, such as a laser beam printer. A vector representation of a graphic object is a description of the graphic object in terms of an object outline, typically in the form of straight lines (vectors). Conversely, a raster representation of a graphic object consists of pixels needed to render the graphic object on the display device. The pixels of the raster representation are part of a pixel grid of the display device. The pixel grid defines locations of the pixels and resolution of those pixels, known as the device resolution.
Graphic objects in a vector representation are known as vector objects. One method of transforming a vector object to a raster representation is referred to as Bresenham's algorithm. For each vector of a vector object, Bresenham's algorithm determines pixels that correspond to the intersection of the vector with each scanline of the pixel grid. A scanline is a row of pixels in the pixel grid of the display device. Once the position of the start of the vector is known, the pixel at the intersection of the vector with each scanline is determined by incrementing the position at a previous scanline intersection by an offset that represents the slope of the vector. The offset contains an integer part and a fractional part. The integer part determines the pixels that are activated by the vector and the fractional part accumulates an error value. Once the error value exceeds a certain threshold the integer part is incremented an additional time.
Bresenham's algorithm is also used to determine the appearance of an image when the image is rendered at device resolution. The image to be rendered to the pixel grid of the device is known as a source image. The rendered image at device resolution is known as a destination image. Due to differences between the resolution of the source image and the device resolution, and the image transformation (translation, scaling and/or rotation) to be applied to the source image, mappings between source image pixels and destination image pixels (known as pixel mappings) are not always straightforward. Using Bresenham's algorithm, the location of the source image pixel that corresponds to a destination image pixel may be determined by incrementing the location of the previous source image pixel by an offset that is calculated from the image transformation. Again, the offset contains an integer part which determines the discrete mapping from destination image pixels to source image pixels; and a fractional part which accumulates an error value.
The methods discussed above require offset and error accumulation calculations to be performed for every pixel in a destination image.
One alternative to using Bresenham's algorithm for rendering images, when image transformation contains no rotation, is to pre-calculate the pixel mappings for one row of destination image pixels in the horizontal direction and one column of destination image pixels in the vertical direction. For cases where the image transformation does not contain any rotation, the two sequences of pixel mappings are sufficient to determine the location of the source image pixel for any destination image pixel, avoiding the need to calculate the source image pixel for every destination image pixel in the destination image. However, such a method requires additional memory to store sequences of pixel mappings for the width and height of the destination image.
A similar method may be used when drawing vector objects. In such a method, pixel offsets for each scanline of a vector may be predetermined. Like the above method for predetermination of sequences of pixel mappings, such a predetermination method reduces the amount of calculations required to render the vectors. However, such a method also generates a large amount of offset data that must be stored in memory.
Thus, a need clearly exists for an encoding method that represents a mapping between vector objects or source image pixels and destination image pixels, that is faster and more efficient than the prior art.